package com.esunny.fptree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;

/**
 * FreqPrefixTree 辅助方法
 * 
 * @author jenvin 2012-7-27 上午12:07:10
 */
public class FreqPrefixTrees {

    private static final Log log = LogFactory.getLog(FreqPrefixTrees.class);

    /**
     * 从FP-Tree中找出 item 频繁项
     * 
     * @param tree
     * @param item
     * @return
     */
    public static List<Result> findFpResult(FreqPrefixTree tree, Item item, int minSupport) {
        if (tree == null) throw new NullPointerException("tree");
        if (item == null) throw new NullPointerException("item");

        // 寻找item的条件模式基CPB，放入transRecords中
        List<List<String>> transRecords = new LinkedList<List<String>>();
        TreeNode backnode = item.getLinkNode();

        while (backnode != null) {
            int counter = backnode.getCount();
            List<String> prenodes = new ArrayList<String>();
            TreeNode parent = backnode;
            // 遍历backnode的祖先节点，放到prenodes中
            while ((parent = parent.getParent()).getName() != null) {
                prenodes.add(parent.getName());
            }
            while (counter-- > 0) {
                transRecords.add(prenodes);// 重复加counter 次，便于后面构造条件FP-tree
            }
            backnode = backnode.getNextLink();
        }

        FreqItems cpbItems = new FreqItems(transRecords, minSupport);
        FreqPrefixTree cpbRoot = new FreqPrefixTree(transRecords, cpbItems);
        if (cpbRoot.getRoot() != null && cpbRoot.getNodeSize() > 0) {
            Map<List<String>, Integer> prePatterns = findPrePattern(cpbRoot, minSupport);
            if (prePatterns != null) {
                if (log.isInfoEnabled()) {
                    StringBuilder sb = new StringBuilder();
                    sb.append("freq result [item=" + item.getName() + ",minSupport=" + minSupport + "]:\n");
                    for (Entry<List<String>, Integer> entry : prePatterns.entrySet()) {
                        sb.append(entry.getKey() + " freq:" + entry.getValue() + "\n");
                    }
                    log.info(sb.toString());
                }
                return toResult(prePatterns);
            }
        }
        if (log.isInfoEnabled()) {
            log.info("no freq result [item=" + item.getName() + ",minSupport=" + minSupport + "]:\n");
        }
        return null;
    }

    private static List<Result> toResult(Map<List<String>, Integer> map) {
        if (map == null || map.size() == 0) return null;
        List<Result> list = new ArrayList<Result>();
        Map<String, Integer> tmpMap = new HashMap<String, Integer>();
        for (Entry<List<String>, Integer> entry : map.entrySet()) {
            for (String s : entry.getKey()) {
                if (tmpMap.containsKey(s)) {
                    tmpMap.put(s, tmpMap.get(s) + entry.getValue());
                } else {
                    tmpMap.put(s, entry.getValue());
                }
            }
        }
        for (Entry<String, Integer> e : tmpMap.entrySet()) {
            Result r = new Result();
            r.setFreqValue(e.getValue());
            r.setName(e.getKey());
            list.add(r);
        }
        Collections.sort(list, new Comparator<Result>() {

            @Override
            public int compare(Result o1, Result o2) {
                return o2.getFreqValue() - o1.getFreqValue();
            }
        });
        return list;
    }

    /**
     * 4.1 从一棵FP-Tree上找到所有的前缀模式
     * 
     * @param root
     * @return
     */
    private static Map<List<String>, Integer> findPrePattern(FreqPrefixTree root, int minSupport) {
        Map<List<String>, Integer> patterns = null;
        List<TreeNode> children = root.getRoot().getChilds();
        if (children != null) {
            patterns = new HashMap<List<String>, Integer>();
            for (TreeNode child : children) {
                // 找到以child为根节点的子树中的所有长路径（所谓长路径指它不是其他任何路径的子路径）
                LinkedList<LinkedList<TreeNode>> paths = buildPaths(child);
                if (paths != null) {
                    for (List<TreeNode> path : paths) {
                        Map<List<String>, Integer> backPatterns = combination(path);
                        Set<Entry<List<String>, Integer>> entryset = backPatterns.entrySet();
                        for (Entry<List<String>, Integer> entry : entryset) {
                            List<String> key = entry.getKey();
                            int c1 = entry.getValue();
                            int c0 = 0;
                            if (patterns.containsKey(key)) {
                                c0 = patterns.get(key).byteValue();
                            }
                            patterns.put(key, c0 + c1);
                        }
                    }
                }
            }
        }

        // 过滤掉那些小于MinSup的模式
        Map<List<String>, Integer> rect = null;
        if (patterns != null) {
            rect = new HashMap<List<String>, Integer>();
            Set<Entry<List<String>, Integer>> ss = patterns.entrySet();
            for (Entry<List<String>, Integer> entry : ss) {
                if (entry.getValue() >= minSupport) {
                    rect.put(entry.getKey(), entry.getValue());
                }
            }
        }
        return rect;
    }

    /**
     * 4.1.1 找到从指定节点（root）到所有可达叶子节点的路径
     * 
     * @param stack
     * @param root
     */
    private static LinkedList<LinkedList<TreeNode>> buildPaths(TreeNode root) {
        LinkedList<LinkedList<TreeNode>> paths = null;
        if (root != null) {
            paths = new LinkedList<LinkedList<TreeNode>>();
            List<TreeNode> children = root.getChilds();
            if (children != null) {
                // 在从树上分离单条路径时，对分叉口的节点，其count也要分到各条路径上去
                // 条件FP-Tree是多枝的情况
                if (children.size() > 1) {
                    for (TreeNode child : children) {
                        int count = child.getCount();
                        LinkedList<LinkedList<TreeNode>> ll = buildPaths(child);
                        for (LinkedList<TreeNode> lp : ll) {
                            TreeNode prenode = new TreeNode(root.getName());
                            prenode.setCount(count);
                            lp.addFirst(prenode);
                            paths.add(lp);
                        }
                    }
                }
                // 条件FP-Tree是单枝的情况
                else {
                    for (TreeNode child : children) {
                        LinkedList<LinkedList<TreeNode>> ll = buildPaths(child);
                        for (LinkedList<TreeNode> lp : ll) {
                            lp.addFirst(root);
                            paths.add(lp);
                        }
                    }
                }
            } else {
                LinkedList<TreeNode> lp = new LinkedList<TreeNode>();
                lp.add(root);
                paths.add(lp);
            }
        }
        return paths;
    }

    /**
     * 4.1.2 生成路径path中所有元素的任意组合，并记下每一种组合的count--其实就是组合中最后一个元素的count，因为我们的组合算法保证了树中 （或path中)和组合中元素出现的相对顺序不变
     * 
     * @param path
     * @return
     */
    private static Map<List<String>, Integer> combination(List<TreeNode> path) {
        if (path.size() > 0) {
            // 从path中移除首节点
            TreeNode start = path.remove(0);
            // 首节点自己可以成为一个组合，放入rect中
            Map<List<String>, Integer> rect = new HashMap<List<String>, Integer>();
            List<String> li = new ArrayList<String>();
            li.add(start.getName());
            rect.put(li, start.getCount());

            Map<List<String>, Integer> postCombination = combination(path);
            if (postCombination != null) {
                Set<Entry<List<String>, Integer>> set = postCombination.entrySet();
                for (Entry<List<String>, Integer> entry : set) {
                    // 把首节点之后元素的所有组合放入rect中
                    rect.put(entry.getKey(), entry.getValue());
                    // 首节点并上其后元素的各种组合放入rect中
                    List<String> ll = new ArrayList<String>();
                    ll.addAll(entry.getKey());
                    ll.add(start.getName());
                    rect.put(ll, entry.getValue());
                }
            }

            return rect;
        } else {
            return null;
        }
    }

    public static void main(String[] args) throws IOException {
        InputStreamReader fr = new InputStreamReader(FreqPrefixTrees.class.getResourceAsStream("data.txt"));
        BufferedReader br = new BufferedReader(fr);
        String line = null;
        List<List<String>> records = new LinkedList<List<String>>();
        List<String> record;
        while ((line = br.readLine()) != null) {
            if (line.trim() != "") {
                record = new LinkedList<String>();
                String[] items = line.split("[，|,]");
                for (String item : items) {
                    record.add(item);
                }
                records.add(record);
            }
        }

        int minSupport = 3;
        FreqItems items = new FreqItems(records, minSupport);
        System.out.println(items.toString());
        FreqPrefixTree tree = new FreqPrefixTree(records, items);
        System.out.println(tree.toString());
        for (Item i : items) {
            List<Result> lstResults = FreqPrefixTrees.findFpResult(tree, i, minSupport);
            System.out.print(i.getName() + " 推荐:");
            System.out.println(lstResults);
        }

    }
}
